COMMENT ⊗   VALID 00006 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\input acphdr %The front matter:
C00004 00003	\setcount0-5  % roman numeral page numbers
C00018 00004	\runninglefthead{NOTES ON THE EXERCISES}
C00031 00005	\runningrighthead{CONTENTS} \section{}
C00036 00006	%The following page will contain the frontispiece, no page numbers
C00037 ENDMK
C⊗;
\input acphdr %The front matter:
% The following is page iv (the copyright notice etc.):
\corners
\vfill
\ninepoint
\hjust{This book is in the}
\vskip 3pt
\hjust{\:<ADDISON-WESLEY SERIES IN}
\vskip 3pt
\hjust{\:<COMPUTER SCIENCE AND INFORMATION PROCESSING}
\vskip .5in
\hjust{Consulting Editors}
\vskip 3pt
\hjust{{\:mRICHARD S. VARGA} and {\:mMICHAEL A. HARRISON}}
\vfill
\noindent\:m
\def\\{\hskip 0pt plus 4pt}
COPYRIGHT $\copyright$ $1978$, $1969$
BY ADDISON-WESLEY PUBLISHING COMPANY, INC. \\
ALL RIGHTS RESERVED. \\
NO PART OF THIS PUBLICATION MAY BE REPRODUCED, \\STORED IN A RE\-TRIEVAL SYSTEM, \\
OR TRANSMITTED, \\IN ANY FORM OR BY ANY MEANS, \\ELECTRONIC, \\MECHANICAL, \\
PHOTOCOPYING, \\
RECORDING, \\OR OTHERWISE, \\WITHOUT THE PRIOR WRITTEN PERMISSION OF THE
PUBLISHER. \\
PRINTED IN THE UNITED STATES OF AMERICA. \\
PUBLISHED SIMULTANEOUSLY IN CANADA.\par
\vskip 3pt
\hjust{LIBRARY OF CONGRESS CATALOG CARD NO. $67$-$26020$.}
\eject
\setcount0-5  % roman numeral page numbers
\titlepage
\runninglefthead{PREFACE}
\corners
\vskip 1in plus 30pt minus 10pt
\rjustline{\:;PREFACE}
\vskip 1cm plus 30pt minus 10pt
\quoteformat{O dear Ophelia!\cr
I am ill at these numbers:\cr
I have not art to reckon my groans.\cr}
\author{Hamlet (Act II, Sc. 2, Line 120)}
\vskip 1cm plus 30pt minus 10pt
\runningrighthead{PREFACE} \section{}
\noindent\tenpoint
T{\:cHE ALGORITHMS} discussed in this book deal directly with numbers; yet I
believe they are properly called {\sl seminumerical}, because they lie on the
borderline between numeric and symbolic calculation. Each algorithm not only
computes the desired answers to a problem, it also is intended to blend
well with the internal operations of a digital computer. In many cases a person
will not be able to appreciate the beauty of such an algorithm unless he also has
some knowledge of a computer's machine language; the efficiency of the corresponding
machine program is a vital factor that cannot be divorced from the algorithm
itself. The problem is to find the best ways to make computers deal with numbers,
and this involves tactical as well as numerical considerations. Therefore the
subject matter of this book is unmistakably a part of computer science, as well as
of numerical mathematics.

Some people working in ``higher levels'' of numerical analysis will regard the
topics treated here as the domain of system programmers. Other people working in
``higher levels'' of system programming will regard the topics treated here as
the domain of numerical analysts. But I hope that there are a few people left who
will want to look carefully at these basic methods; although the methods reside
perhaps on a
low level, they underlie all of the more grandiose applications of computers to
numerical problems, so it is important to know them well. We are concerned here
with the interface between numerical mathematics and computer programming,
and it is the mating of both types of skills that makes the subject so interesting.

There is a noticeably higher percentage of mathematical material in this book than
in other volumes of this series, because of the nature of the subjects treated. In
most cases the necessary mathematical topics are developed here starting almost
from scratch (or from results proved in Volume 1), but in some easily-recognizable
sections a knowledge of calculus has been assumed.

This volume comprises Chapters 3 and 4 of the complete series. Chapter 3 is
concerned with ``random numbers'': it is not only a study of various methods
for generating random sequences, it also investigates statistical tests for
randomness, as well as the transformation of uniform random numbers into other
types of random quantities; the latter subject illustrates how random numbers
are used in practice. I have also included a section about the nature of
randomness itself. Chapter 4 is my attempt to tell the fascinating story of what
mankind has been able to learn about the processes of arithmetic, after centuries
of progress. It discusses various systems for representing numbers, and how to
convert between them; and it treats arithmetic on floating-point numbers, high-\!
precision integers, rational fractions, polynomials, and power series, including the
questions of factoring and finding greatest common divisors.

Each of Chapters 3 and 4 can be used as the basis of a one-semester college course
at the junior to graduate level. Although courses on ``Random Numbers'' and on
``Arithmetic'' are not presently a part of many college curricula, I believe the
reader will find that the subject matter of these chapters lends itself nicely to
a unified treatment of material that has real educational value. My own experience
has been that these courses are a good means of introducing elementary probability
theory and number theory to college students; nearly all of the topics usually
treated in such introductory courses arise naturally in connection with
applications,
and the presence of these applications can be an important motivation that helps
the student to learn and to appreciate the theory. Furthermore, each chapter gives
a few hints of more advanced topics that will whet the appetite of many students
for further mathematical study.

For the most part this book is self-contained, except for occasional discussions
relating to the \MIX\ computer explained in Volume 1. Appendix B contains a summary
of the mathematical notations used, some of which are a little different from
those found in traditional mathematics books.

In addition to the acknowledgments made in the preface to Volume 1, I would like to
express deep appreciation to Elwyn R. Berlekamp, John Brillhart, George E. Collins,
Stephen A. Cook, D. H. Lehmer, M. Donald MacLaren, Mervin E. Muller, Kenneth B.
Stolarsky, and H. Zassenhaus, who have generously devoted considerable time to
reading portions of the preliminary manuscript, and who have suggested many
valuable improvements.

\yyskip
\hjust to size{\sl Princeton, New Jersey \hfill \rm D. E. K.}
\hjust{\sl October 1968}
\sectionskip
\runningrighthead{PREFACE TO THE SECOND EDITION} \section{}
\sectionbegin{Preface to the Second Edition}
My first plan, when beginning to prepare this new edition, was to make it
like the second edition of Volume 1: I went through the entire book and tried to
improve every page without greatly perturbing the page numbering.
But the number of improvements turned out to be so great that the entire book
needed to be typeset again. As a result, I decided to make this book the first
test case for a new computer typesetting system I have been developing. I hope that
most readers will like the slight changes in format, since my aim has been to
produce a book whose typography is of the highest possible quality---superior even
to the fine appearance of the previous editions, in spite of the fact that a
computer is now involved. If all goes well, the third edition of Volume 1 and the
second edition of Volume 3 and all editions of Volumes 4 through 7 will be published
in the present style.

The decision to reset this entire book has freed me from the shackles of the
previous
page numbering, so I have been able to make major refinements and to insert a lot
of new material. I estimate that about 35 percent of the book has changed.
I did try, however,
to keep the exercise numbers from being substantially altered; although many of
the old exercises have been replaced by new and better ones, the new exercises
tend to relate to the same idea as before. The explosive growth
of seminumerical research in recent years has of course made it impossible for
me to insert all of the beautiful ideas in this field that have been discovered
since 1968; but I think that this
edition does contain an up-to-date survey of all the
major paradigms and basic theory of the subject, and it seems reasonable to
believe that very few of the topics discussed here will ever become obsolete.

I am deeply grateful for the advice and unselfish assistance of many readers, too
numerous to mention. In this regard I want to acknowledge especially the help of
several people whose contributions have been really major: R. P. Brent, U. Dieter,
M. J. Fischer,
R. W. Gosper, D. C. Hoaglin, W. M. Kahan, J. F. Reiser, A. G. Waterman, S. Winograd,
and M. C. Wunderlich. Furthermore Marion Howe and other people in the
Addison-Wesley production department have
been enormously helpful in untangling literally
thousands of hand-written inserts so that a very chaotic manuscript has come out
looking reasonably well-organized.
I suppose some mistakes still remain, or have crept in, and
I would like to fix them; therefore I will cheerfully pay $\$$2.00 reward to the
first finder of each technical, typographical, or historical error.

\yyskip
\hjust to size{\sl Stanford, California \hfill \rm D. E. K.}
\hjust{\sl May 1978}
\vfill
\quoteformat{`Defendit numerus,' {\rm[there is safety in numbers]}\cr
is the maxim\cr of the foolish;\cr
`Deperdit numerus,' {\rm[there is ruin in numbers]}\cr
of the wise.\cr}
\author{C. C. COLTON (1820)}
\eject
\ifeven0{\advcount0}\else{} %move to a right-hand page
\titlepage
\runninglefthead{NOTES ON THE EXERCISES}
\runningrighthead{NOTES ON THE EXERCISES} \section{}
\corners
\vskip 1in plus 30pt minus 10pt
\rjustline{\:;NOTES ON THE EXERCISES}
\vskip 1cm plus 30pt minus 10pt
\noindent\tenpoint
T{\:cHE EXERCISES} in this set of books have been designed for self-study as well
as classroom study. It is difficult, if not impossible, for anyone to learn a
subject purely by reading about it, without applying the information to specific
problems and thereby being encouraged to think about what has been read.
Furthermore, we all learn best the things that we have discovered for ourselves.
Therefore the exercises form a major part of this work; a definite attempt has
been made to keep them as informative as possible and to select problems that
are enjoyable to solve.

In many books, easy exercises are found mixed randomly among extremely difficult
ones. This is sometimes unfortunate because readers like to know in advance how long
a problem ought to take---otherwise they
may just skip over all the problems. A classic example
of such a situation is the book {\sl Dynamic Programming} by Richard Bellman;
this is an important, pioneering work in which a group of problems is collected
together at the end of some chapters under the heading ``Exercises and Research
Problems,'' with extremely trivial questions appearing in the midst of deep,
unsolved problems. It is rumored that someone once asked Dr. Bellman how to
tell the exercises apart from the research problems, and he replied, ``If you can
solve it, it is an exercise; otherwise it's a research problem.''

Good arguments can be made for including both research problems and very easy
exercises in a book of this kind; therefore, to save the reader from the possible
dilemma of determining which are which, {\sl rating numbers} have been provided
to indicate the level of difficulty. These numbers have the following
general significance:

\yyskip
\ninepoint\hjust{\sl Rating\ \ Interpretation}
\penalty1000\vskip 3pt plus 3pt
\def\\#1#2 {\yskip\noindent\hangindent 1cm\hjust to 1cm{\hfill\it#1#2\hfill}}
\\00 An extremely easy exercise, which can be answered immediately if the
material of the text has been understood, and which can almost always be
worked ``in your head.''\par
\\10 A simple problem, which makes a person think over the material just read,
but which is by no means difficult. It should be possible to do this in one
minute at most; pencil and paper may be useful in obtaining the solution.\par
\\20 An average problem, which tests basic understanding of the text material,
but which may take about fifteen or twenty minutes to answer completely.\par
\\30 A problem of moderate difficulty and/or complexity, which may involve over
two hours' work to solve satisfactorily.\par
\\40 Quite a difficult or lengthy problem, which is perhaps suitable for a term
project in classroom situations. It is expected that a student will be able to
solve the problem in a reasonable amount of time, but the solution is not
trivial.\par
\\50 A research problem, which (to the author's knowledge at the time of
writing) has not yet been solved satisfactorily. If the reader has found an
answer to this problem, he or she is urged to write it up for publication;
furthermore, the author of this book would appreciate hearing about the solution
as soon as possible (provided that it is correct).

\yyskip\tenpoint
By interpolation in this ``logarithmic'' scale, the significance of other rating
numbers becomes clear. For example, a rating of {\it 17} would indicate an
exercise that is a bit simpler than average. Problems with a rating of {\it 50}
that are subsequently solved by some reader may appear with a {\it 45} rating in
later editions of the book.

The author has earnestly tried to assign accurate rating numbers, but it is
difficult for the person who makes up a problem to know just how formidable
it will be for someone else to solve it; and everyone has more aptitude for
certain types of problems than for others. It is hoped that the rating numbers
represent a good guess as to the level of difficulty, but they should be taken
as general guidelines, not as absolute indicators.

This book has been written for readers with varying degrees of mathematical
training and sophistication; as a result, some of the exercises are intended
only for the use of more mathematically inclined readers. The rating
is preceded by an {\it M} if the exercise involves mathematical concepts or
motivation to a greater extent than necessary for someone who is primarily
interested only in programming the algorithms themselves. An exercise is marked
with the letters ``{\it HM}\/'' if its solution necessarily involves a knowledge of
calculus or other higher mathematics not developed in this book. An ``{\it HM}\/''
designation does {\sl not} necessarily imply difficulty.

Some exercises are preceded by an arrowhead, ``$\char'770$''; this designates
problems that are especially instructive and that are especially recommended.
Of course, no reader/student is expected to work {\sl all} of the exercises,
so those that are perhaps the most valuable have been singled out.\xskip(This is not
meant to detract from the other exercises!)\xskip
Each reader should at least make an
attempt to solve all of the problems whose rating is {\it 10} or less; and the
arrows may help to indicate which of the problems with a higher rating should
be given priority.

Solutions to most of the exercises appear in the answer section. Please use them
wisely; do not turn to the answer until you have made a genuine effort to solve
the problem by yourself, or unless you do not have time to work this particular
problem. {\sl After} getting your own solution or giving the problem a decent
try, you may find the answer instructive and helpful. The solution given will often
be quite short, and it will sketch the details under the assumption that you
have earnestly tried to solve it by your own means first. Sometimes the solution
gives less information than was asked; often it gives more. It is quite
possible that you may have a better answer than the one published here, or
you may have found an error in the published solution; in such a case, the
author will be pleased to know the details. Later editions
of this book will give the improved solutions together with the solver's name
where appropriate.

When working an exercise you may generally use the answers to previous exercises,
unless specifically forbidden from doing so.
The rating numbers have been assigned with
this in mind; thus it is possible for exercise $n+1$ to have a lower rating than
exercise $n$, even though it includes the result of exercise $n$ as a special case.

\sectionskip
\ninepoint
\vjust{\hrule
\hjust to size{\vrule\hskip .5cm
\valign{\vskip 9pt#\vskip9pt\cr
\hjust{Summary of codes:}
\vfill
\halign{\lft{#}\quad⊗\lft{#}\cr
$\char'770$⊗Recommended\cr
{\it M}⊗Mathematically oriented\cr
{\it HM}⊗Requiring ``higher math''\cr}\cr
\noalign{\hfill}
\halign{{\it#}\quad⊗\lft{#}\cr
00⊗Immediate\cr
10⊗Simple (one minute)\cr
20⊗Medium (quarter hour)\cr
30⊗Moderately hard\cr
40⊗Term project\cr
50⊗Research problem\cr}\cr} % that last \cr} ends the \valign
\hskip 1cm \vrule} % end of the \hjust to size
\hrule} % end of the \vjust

\exbegin{EXERCISES}
\trexno 1. [00] What does the rating ``{\it M20}\/'' mean?
\exno 2. [10] Of what value can the exercises in a textbook be to the reader?
\exno 3. [M50] Prove that when $n$ is an integer, $n>2$, the equation
$x↑n+y↑n=z↑n$ has no solution in positive integers $x,y,z$.

\vfill
\quoteformat{Exercise is the beste intrument in learnyng.\cr}
\author{ROBERT RECORDE, The Whetstone of Witte (1557)}
\eject
\runningrighthead{CONTENTS} \section{}
\ifeven0{}\else{\advcount0}
\titlepage\corners
\vjust to 80pt{\vfill\rjustline{\:;CONTENTS}\vfill}
{   % Beginning of special definitions for the table of contents
\def\\#1#2{\hjust to size{#1\leaders\hjust to .5cm{\hfill.\hfill}\hfill
	\hjust to 16.6pt{\hfill#2}}}
\def\a#1.#2.{\hjust to 7mm{#1.#2.}}
\def\b#1.#2.#3.{\hjust to 17mm{\hskip 7mm\hjust to 9.9999mm{#1.#2.#3.}}}
\def\c#1.#2.#3.#4.{\hjust to 30mm{\hskip 17mm\hjust to 12.9999mm{#1.#2.#3.#4.}}}
\ninepoint
{\:<\\{Chapter 3---Random Numbers}{1}}
\vskip 3pt
\\{\a3.1.Introduction}{1}
\\{\a3.2.Generating Uniform Random Numbers}{0}
\\{\b3.2.1.The Linear Congruential Method}{0}
\\{\c3.2.1.1.Choice of modulus}{00}
\\{\c3.2.1.2.Choice of multiplier}{00}
\\{\c3.2.1.3.Potency}{00}
\\{\b3.2.2.Other Methods}{00}
\\{\a3.3.Statistical Tests}{00}
\\{\b3.3.1.General Test Procedures for Studying Random Data}{00}
\\{\b3.3.2.Empirical Tests}{00}
\\{\b{\star3}.3.3.Theoretical Tests}{00}
\\{\b3.3.4.The Spectral Test}{00}
\\{\a3.4.Other Types of Random Quantities}{000}
\\{\b3.4.1.Numerical Distributions}{000}
\\{\b3.4.2.Random Sampling and Shuffling}{000}
\\{\a{\star3}.5.What is a Random Sequence?}{000}
\\{\a3.6.Summary}{000}
\vskip 12pt plus 6pt
{\:<\\{Chapter 4---Arithmetic}{000}}
\vskip 3pt
\\{\a4.1.Positional Number Systems}{000}
\\{\a4.2.Floating-Point Arithmetic}{000}
\\{\b4.2.1.Single-Precision Calculations}{000}
\\{\b4.2.2.Accuracy of Floating-Point Arithmetic}{000}
\\{\b{\star4}.2.3.Double-Precision Calculations}{000}
\\{\b4.2.4.Distribution of Floating-Point Numbers}{000}
\\{\a4.3.Multiple-Precision Arithmetic}{000}
\\{\b4.3.1.The Classical Algorithms}{000}
\\{\b{\star4}.3.2.Modular Arithmetic}{000}
\\{\b{\star4}.3.3.How Fast Can We Multiply?}{000}
\\{\a4.4.Radix Conversion}{000}
\\{\a4.5.Rational Arithmetic}{000}
\\{\b4.5.1.Fractions}{000}
\\{\b4.5.2.The Greatest Common Divisor}{000}
\\{\b{\star4}.5.3.Analysis of Euclid's Algorithm}{000}
\\{\b4.5.4.Factoring into Primes}{000}
\eject
\vskip 80pt
\\{\a4.6.Polynomial Arithmetic}{000}
\\{\b4.6.1.Division of Polynomials}{000}
\\{\b{\star4}.6.2.Factorization of Polynomials}{000}
\\{\b4.6.3.Evaluation of Powers}{000}
\\{\b4.6.4.Evaluation of Polynomials}{000}
\\{\a{\star4}.7.Manipulation of Power Series}{000}
\vskip 12pt plus 6pt
{\:<\\{Answers to Exercises}{000}}
\vskip 12pt plus 6pt
{\:<\\{Appendix A---Tables of Numerical Quantities}{000}}
\vskip 3pt
\def\a#1.{\hjust to 7mm{#1.}}
\\{\a1.Fundamental Constants (decimal)}{000}
\\{\a2.Fundamental Constants (octal)}{000}
\\{\a3.Harmonic Numbers, Bernoulli Numbers, Fibonacci Numbers}{000}
\vskip 12pt plus 6pt
{\:<\\{Appendix B---Index to Notations}{000}}
\vskip 12pt plus 6pt
{\:<\\{Index and Glossary}{000}}
\vfill
\eject} %This ends the table of contents
%The following page will contain the frontispiece, no page numbers